package Search_07;

/*
 * @Author 罗
 * @date 2020/3/19 - 5:39 下午
 *
 */

import org.junit.Test;

import java.util.Arrays;

public class FibonacciSearch_04 {

    @Test
    public void test() {
        int[] array = {1, 8, 10, 89, 1000, 1234};
        getFib(10);
        int[] fib = new int[10];
        getFibByRecursion(fib, 0);
        System.out.println(Arrays.toString(fib));
        System.out.println(fibSearch(array, 8));
    }

    /**
     * 斐波那契数列
     * <p>
     * 由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到 （F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。
     * -1 的目的是为了得到mid
     * 该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。
     * 从而中间位置为mid=low+F(k-1)-1
     * <p>
     * 类似的，每一子段也可以用相同的方式分割，但顺序表长度n不一定刚好等于F[k]-1，
     * 所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，
     * 由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。
     * f(k) = f(k-1) + f(k-2)
     * f(k)-1 = (f(k-1)-1) + (f(k-2)-1)  + 1
     * mid = low + F(k-1) -1
     *
     * @param array
     * @param findValue
     * @return
     */
    public static int fibSearch(int[] array, int findValue) {
        int low = 0;
        int high = array.length - 1;
        /*
         * 斐波那契分割数值的下标
         * */
        int k = 0;

        int mid = 0;
        /*
         * 斐波那契数列长度可能会不够，要注意扩充
         * */
        int[] fib = getFib(6);
        /*
         * 获取斐波那契分割数值的下标
         * 每一子段也可以用相同的方式分割，但顺序表长度n不一定刚好等于F[k]-1，
         * 所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，
         * 由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。
         * */
        while (high > fib[k] - 1) {
            k++;
        }
        /* 数组的长度要等于斐波那契数列的某元素   [1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...] 之一
         *    才能使用斐波那契查找
         * 执行完之后fib[k] 的值 可能会 大于 array.length
         * 因此需要利用Arrays类，构造一个新的数组，并指向temp[]
         * 执行完之后，新数组temp的长度就是fib[k]
         *      斐波那契数列的长度和数组temp的长度一致
         *  {1, 8, 10, 89, 1000, 1234}的长度是 6，大于6且最接近6的斐波那契数列是8
         *  需要把数列扩充到8个
         * @param array 用于拷贝的源数组
         * @param fib[k] array的新长度，若新长度比原来array的长度长，不足的部分用0补齐
         * */
        int[] temp = Arrays.copyOf(array, fib[k]);
        /* array = {1, 8, 10, 89, 1000, 1234, 0, 0} 扩充完成
         * 但是实际上需要用array[array.length-1]来填充temp，而不是用0
         * 因为后续斐波那契查找时，可能会用到比较
         * 即    array = {1, 8, 10, 89, 1000, 1234, 1234, 1234}
         */
        for (int i = array.length; i < temp.length; i++) {
            temp[i] = array[array.length - 1];
        }
        /*
         * 用while来查找findValue
         * 只要还没有超越源数组array的长度，就可以一直查找
         * */
        while (low <= high) {
            /*
             * mid无论向左还是向右，都始终保持黄金分割点
             * */
            mid = low + fib[k - 1] - 1;
            if (findValue < temp[mid]) {
                /*
                 * 向mid之前查找
                 * */
                high = mid - 1;
                /*
                 * 全部元素  =  mid之前的元素 + mid之后的元素
                 *      即f(k) = f(k-1) + f(k-2)
                 *  因为前面有f(k-1)个元素，所以可以继续拆分
                 *      f(k-1) = f(k-2) + f(k-3)
                 *       就是在f(k-1)之前继续查找
                 * 下次 mid =  f(k-1-1) -1
                 * */
                k--;
            } else if (findValue > temp[mid]) {
                /*
                 * 向temp[mid]的后面继续查找
                 * */
                low = mid + 1;
                /*
                 *  全部元素  =  mid之前的元素 + mid之后的元素
                 *      即f(k) = f(k-1) + f(k-2)
                 *  因为后面有f(k-2)个元素，所以可以继续拆分
                 *      f(k-1) = f(k-3) + f(k-4)
                 *  即在f(k-2)之前继续查找 k = k - 2
                 *  下次 mid = f(k-1-2) - 1
                 * */
                k = k - 2;

            } else {
                /*
                 * 找到了
                 * 需要确定返回的是哪一个下标
                 * */
                if (mid <= high) {
                    return mid;
                } else {
                    /*
                     * 返回high是因为之前temp多余的部分用high填充了
                     * */
                    return high;
                }
            }
        }
        return -1;
    }

    /**
     * 使用非递归方式获取斐波那契数列
     *
     * @param length 斐波那契数列的长度
     * @return 返回斐波那契数列
     */
    public static int[] getFib(int length) {
        /*
         * 后面会用到斐波那契数列，这里先创建一个
         *
         * */
        int[] fib = new int[length];
        fib[0] = 1;
        fib[1] = 1;
        for (int i = 2; i < length; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        System.out.println(Arrays.toString(fib));
        return fib;
    }

    /**
     * 递归方式获取斐波那契数列
     *
     * @param fib
     * @param count
     * @return
     */
    public static int[] getFibByRecursion(int[] fib, int count) {
        if (count >= fib.length) {
            return fib;
        }
        if (count < 2) {
            fib[0] = 1;
            fib[1] = 1;
            count = 2;
        }

        fib[count] = fib[count - 1] + fib[count - 2];
        count++;
        return getFibByRecursion(fib, count);
    }
}
